# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2023/3/3 14:30
@FileName      : ST算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
n = 100001
a = list(range(1, 1001))
dp = [[0] * 40 for s in range(n)]


def log2(num):
    k = 0
    while num >> k: k += 1
    return k


def st_init():
    global dp
    P = log2(len(a))
    for i in range(len(a)): dp[i][0] = a[i]
    for k in range(1, P):
        for s in range(0, len(a) + 1 - (1 << k)):
            dp[s][k] = max(dp[s][k - 1], dp[s + (1 << (k - 1))][k - 1])


st_init()


def st_query(l, r):
    k = log2(r - l + 1) - 1
    return max(dp[l][k], dp[r + 1 - (1 << k)][k])


print(st_query(8, 197))
